/**
 * 给你一个大小为 m x n 的二进制矩阵 grid 。
 *
 * 岛屿是由一些相邻的1(代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设grid 的四个边缘都被 0（代表水）包围着。
 *
 * 岛屿的面积是岛上值为 1 的单元格的数目。
 *
 * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/max-area-of-island
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode695 {

    public static void main(String[] args) {

        String string = "北艾路1077弄，\n" +
                "\n" +
                "北蔡镇五星村陈家队陈家宅，\n" +
                "\n" +
                "北蔡镇杨桥村西计队金家宅，\n" +
                "\n" +
                "北蔡镇中界村陆家队陆家宅，\n" +
                "\n" +
                "北蔡镇中界村沈家队姚家宅，\n" +
                "\n" +
                "北张家浜路188弄，\n" +
                "\n" +
                "博兴路1663弄，\n" +
                "\n" +
                "博兴路986弄，\n" +
                "\n" +
                "彩云路568弄，\n" +
                "\n" +
                "曹路镇顾三村黄家宅，\n" +
                "\n" +
                "曹路镇光明村沙桥宅，\n" +
                "\n" +
                "曹路镇建新村叶家宅，\n" +
                "\n" +
                "曹路镇联合村路南宅，\n" +
                "\n" +
                "曹路镇联合村西柴场，\n" +
                "\n" +
                "曹路镇民建村南邵家宅，\n" +
                "\n" +
                "曹路镇新光村陆家宅，\n" +
                "\n" +
                "曹路镇迅建村季家宅，\n" +
                "\n" +
                "长岛路1201弄，\n" +
                "\n" +
                "长岛路800弄，\n" +
                "\n" +
                "长清路773弄，\n" +
                "\n" +
                "长清路977弄，\n" +
                "\n" +
                "昌里东路550弄，\n" +
                "\n" +
                "昌里东路80弄，\n" +
                "\n" +
                "昌里路340弄，\n" +
                "\n" +
                "陈邵路101号生活区，\n" +
                "\n" +
                "成山路1488弄，\n" +
                "\n" +
                "成山路1728弄，\n" +
                "\n" +
                "成山路24弄，\n" +
                "\n" +
                "川周公路3010弄，\n" +
                "\n" +
                "川周路8288弄，\n" +
                "\n" +
                "创新西路300弄，\n" +
                "\n" +
                "创业路78弄，\n" +
                "\n" +
                "大团镇团西村，\n" +
                "\n" +
                "德平路1065弄，\n" +
                "\n" +
                "德平路1066弄，\n" +
                "\n" +
                "德平路1125弄，\n" +
                "\n" +
                "德平路730弄，\n" +
                "\n" +
                "丁香路1089弄，\n" +
                "\n" +
                "丁香路1599弄，\n" +
                "\n" +
                "丁香路910弄，\n" +
                "\n" +
                "东建新村，\n" +
                "\n" +
                "东靖路247弄，\n" +
                "\n" +
                "东陆路1268弄，\n" +
                "\n" +
                "东三里桥路190弄，\n" +
                "\n" +
                "东书房路390弄，\n" +
                "\n" +
                "杜鹃路58弄，\n" +
                "\n" +
                "繁锦路688弄，\n" +
                "\n" +
                "芳甸路333弄，\n" +
                "\n" +
                "芳华路188弄，\n" +
                "\n" +
                "芳华路329弄，\n" +
                "\n" +
                "芳华路371弄，\n" +
                "\n" +
                "芳华路411弄，\n" +
                "\n" +
                "芳华路455弄，\n" +
                "\n" +
                "芳华路63号，\n" +
                "\n" +
                "芳芯路312弄，\n" +
                "\n" +
                "高东镇珊黄村苍头宅，\n" +
                "\n" +
                "高东镇先锋村卢家宅，\n" +
                "\n" +
                "高科西路2111弄，\n" +
                "\n" +
                "高科西路3060弄，\n" +
                "\n" +
                "高桥镇陆凌村西凌家宅，\n" +
                "\n" +
                "高桥镇南塘村龚家宅，\n" +
                "\n" +
                "高桥镇南塘村顾家宅，\n" +
                "\n" +
                "高桥镇南塘村姚家宅，\n" +
                "\n" +
                "古棕路168弄，\n" +
                "\n" +
                "海基三路海洋二路交界口工地生活区，\n" +
                "\n" +
                "海鸣路98弄，\n" +
                "\n" +
                "海鹏路301弄，\n" +
                "\n" +
                "海阳路450弄，\n" +
                "\n" +
                "航昌路鹤涟路交界口工地生活区，\n" +
                "\n" +
                "航头镇果园村，\n" +
                "\n" +
                "航绣路50弄，\n" +
                "\n" +
                "合庆镇勤奋村卫家宅，\n" +
                "\n" +
                "和炯路77弄，\n" +
                "\n" +
                "和龙路55弄，\n" +
                "\n" +
                "鹤永路751弄，\n" +
                "\n" +
                "鸿音路正茂路交界口工地生活区，\n" +
                "\n" +
                "沪东路67号，\n" +
                "\n" +
                "沪南路2688弄，\n" +
                "\n" +
                "沪南路3158弄，\n" +
                "\n" +
                "花木街道龙王庙村南杨家堂，\n" +
                "\n" +
                "花木路500弄，\n" +
                "\n" +
                "花山路1001弄，\n" +
                "\n" +
                "环林西路848弄，\n" +
                "\n" +
                "环桥路1136弄，\n" +
                "\n" +
                "环桥路1481弄，\n" +
                "\n" +
                "荟萃新村，\n" +
                "\n" +
                "季景路370弄，\n" +
                "\n" +
                "济阳路65弄，\n" +
                "\n" +
                "金桥路2552弄，\n" +
                "\n" +
                "金湘路201弄，\n" +
                "\n" +
                "金杨路660弄，\n" +
                "\n" +
                "金杨路785弄，\n" +
                "\n" +
                "锦和路289弄，\n" +
                "\n" +
                "锦尊路306号，\n" +
                "\n" +
                "康桥路90弄，\n" +
                "\n" +
                "康桥镇花墙村，\n" +
                "\n" +
                "康桥镇太平村，\n" +
                "\n" +
                "康沈路2132弄，\n" +
                "\n" +
                "康士路15弄，\n" +
                "\n" +
                "蓝村路470弄，\n" +
                "\n" +
                "崂山三村，\n" +
                "\n" +
                "崂山四村，\n" +
                "\n" +
                "历城路100弄，\n" +
                "\n" +
                "连波路26弄，\n" +
                "\n" +
                "莲中路356弄，\n" +
                "\n" +
                "林展路278弄，\n" +
                "\n" +
                "林展路422弄，\n" +
                "\n" +
                "临沂路181弄，\n" +
                "\n" +
                "灵山路1671弄，\n" +
                "\n" +
                "灵山路2011弄，\n" +
                "\n" +
                "凌兆路334弄，\n" +
                "\n" +
                "凌兆路396弄，\n" +
                "\n" +
                "柳杉路99弄，\n" +
                "\n" +
                "龙东大道2895弄，\n" +
                "\n" +
                "龙居路180弄，\n" +
                "\n" +
                "龙阳路1188号，\n" +
                "\n" +
                "罗山路108弄，\n" +
                "\n" +
                "绿林路320弄，\n" +
                "\n" +
                "马樱丹路127弄，\n" +
                "\n" +
                "苗桥路928弄，\n" +
                "\n" +
                "苗桥路935弄，\n" +
                "\n" +
                "明月路888弄，\n" +
                "\n" +
                "南港大道与环湖南三路交界口工地生活区，\n" +
                "\n" +
                "南码头路1136弄，\n" +
                "\n" +
                "欧高路138弄，\n" +
                "\n" +
                "浦城路580弄，\n" +
                "\n" +
                "浦电路218号，\n" +
                "\n" +
                "浦电路221号，\n" +
                "\n" +
                "浦电路29弄，\n" +
                "\n" +
                "浦电路48弄，\n" +
                "\n" +
                "浦东大道136弄，\n" +
                "\n" +
                "浦东大道140弄，\n" +
                "\n" +
                "浦东大道1623弄，\n" +
                "\n" +
                "浦东大道2639弄，\n" +
                "\n" +
                "浦东大道2746弄，\n" +
                "\n" +
                "浦东南路1288号，\n" +
                "\n" +
                "浦东南路4705号，\n" +
                "\n" +
                "浦东南路4950弄，\n" +
                "\n" +
                "浦明路688弄，\n" +
                "\n" +
                "栖霞路190弄，\n" +
                "\n" +
                "清溪路365弄，\n" +
                "\n" +
                "乳山路161弄，\n" +
                "\n" +
                "瑞福路52弄，\n" +
                "\n" +
                "瑞浦路77弄，\n" +
                "\n" +
                "三林路235号，\n" +
                "\n" +
                "三林路88弄，\n" +
                "\n" +
                "三林镇胡巷村张家宅，\n" +
                "\n" +
                "三林镇临江村王家渡队王家渡，\n" +
                "\n" +
                "三林镇临江村筠西队庞家宅，\n" +
                "\n" +
                "三林镇临江村周南队周家宅，\n" +
                "\n" +
                "三林镇南阜村九思队九思堂，\n" +
                "\n" +
                "三林镇天花庵村北陈队大陈家宅，\n" +
                "\n" +
                "三林镇天花庵村南王家队南王家宅，\n" +
                "\n" +
                "三林镇西林村圈门队西林街，\n" +
                "\n" +
                "三林镇西林村万家队西林街，\n" +
                "\n" +
                "三林镇西林村西林队金家宅，\n" +
                "\n" +
                "三林镇懿德村小陈家队小陈家宅，\n" +
                "\n" +
                "三舒路181弄，\n" +
                "\n" +
                "三舒路62弄，\n" +
                "\n" +
                "三旋路506弄，\n" +
                "\n" +
                "上南路4265弄，\n" +
                "\n" +
                "上南路5588号，\n" +
                "\n" +
                "上南路6333弄，\n" +
                "\n" +
                "上南路6500弄，\n" +
                "\n" +
                "上南路6555弄，\n" +
                "\n" +
                "上南路东明路交界口工地生活区，\n" +
                "\n" +
                "上浦路36弄，\n" +
                "\n" +
                "尚博路569弄，\n" +
                "\n" +
                "申江路轲桥路交界口工地生活区，\n" +
                "\n" +
                "申江南路7877号生活区，\n" +
                "\n" +
                "沈梅路123弄，\n" +
                "\n" +
                "盛夏路738弄，\n" +
                "\n" +
                "世博家园大道站路94弄，\n" +
                "\n" +
                "硕川路125弄，\n" +
                "\n" +
                "唐镇大众村中心新村，\n" +
                "\n" +
                "唐镇虹二村盛家宅，\n" +
                "\n" +
                "唐镇吕三村百胜新村，\n" +
                "\n" +
                "唐镇暮二村顾家宅，\n" +
                "\n" +
                "唐镇小湾村北街，\n" +
                "\n" +
                "唐镇小湾村张家老宅，\n" +
                "\n" +
                "唐镇新虹村东包家宅，\n" +
                "\n" +
                "唐镇新虹村陆家宅，\n" +
                "\n" +
                "唐镇新虹村赵家宅，\n" +
                "\n" +
                "唐镇新镇村谢家宅，\n" +
                "\n" +
                "塘桥路551弄，\n" +
                "\n" +
                "微山二村，\n" +
                "\n" +
                "潍坊路246号，\n" +
                "\n" +
                "潍坊路252弄，\n" +
                "\n" +
                "潍坊路262号，\n" +
                "\n" +
                "潍坊路606号，\n" +
                "\n" +
                "潍坊西路1弄，\n" +
                "\n" +
                "五莲路108弄，\n" +
                "\n" +
                "五莲路759弄，\n" +
                "\n" +
                "下南路161弄，\n" +
                "\n" +
                "下南路370弄，\n" +
                "\n" +
                "新场镇果园村，\n" +
                "\n" +
                "新场镇坦东村连南，\n" +
                "\n" +
                "新场镇坦南村，\n" +
                "\n" +
                "新场镇坦西村坦北，\n" +
                "\n" +
                "新浦路673弄，\n" +
                "\n" +
                "新元南路正茂路交界口工地生活区，\n" +
                "\n" +
                "新园路206弄，\n" +
                "\n" +
                "秀康路958弄，\n" +
                "\n" +
                "秀沿路1177弄，\n" +
                "\n" +
                "秀沿路2875弄，\n" +
                "\n" +
                "宣中路621弄，\n" +
                "\n" +
                "雪野路34弄，\n" +
                "\n" +
                "严桥路150弄，\n" +
                "\n" +
                "杨高南路5777弄3支弄，\n" +
                "\n" +
                "杨南路694弄，\n" +
                "\n" +
                "杨思新村，\n" +
                "\n" +
                "杨新路198弄，\n" +
                "\n" +
                "洋泾街道泾南村东唐家宅，\n" +
                "\n" +
                "耀华路331弄，\n" +
                "\n" +
                "耀华路414弄，\n" +
                "\n" +
                "耀华路421弄，\n" +
                "\n" +
                "耀华路500弄，\n" +
                "\n" +
                "耀华路560号，\n" +
                "\n" +
                "永泰路1650弄，\n" +
                "\n" +
                "云山路1039弄，\n" +
                "\n" +
                "枣庄路210弄，\n" +
                "\n" +
                "张江镇劳动村吴家宅北，\n" +
                "\n" +
                "张江镇中心村周家圈宅，\n" +
                "\n" +
                "张杨路1647弄，\n" +
                "\n" +
                "张杨路1673弄，\n" +
                "\n" +
                "招远路19弄，\n" +
                "\n" +
                "赵高路610号，\n" +
                "\n" +
                "周康路169弄，\n" +
                "\n" +
                "周浦镇沈西村，\n" +
                "\n" +
                "周浦镇瓦南村陆弄，\n" +
                "\n" +
                "周泰路32弄，\n" +
                "\n" +
                "周祝公路4022号工地生活区，\n" +
                "\n" +
                "祝桥镇立新村，\n" +
                "\n" +
                "梓康路580弄，\n" +
                "\n" +
                "紫叶路51弄，\n" +
                "\n" +
                "邹平路191号工地生活区";

        int length = string.split("，").length;
        System.out.println(string.split("，")[0]);

        LeetCode695 leetCode695 = new LeetCode695();
        int[][] grid = new int[][]{{0,0,1,0,0,0,0,1,0,0,0,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,1,1,0,1,0,0,0,0,0,0,0,0},
                {0,1,0,0,1,1,0,0,1,0,1,0,0},
                {0,1,0,0,1,1,0,0,1,1,1,0,0},
                {0,0,0,0,0,0,0,0,0,0,1,0,0},
                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                {0,0,0,0,0,0,0,1,1,0,0,0,0}};
        System.out.println(leetCode695.maxAreaOfIsland(grid));
    }

    public int maxAreaOfIsland(int[][] grid){
        int max = method1(grid);
        return max;
    }

    /**
     * 解题思路1：
     * 深度优先算法
     *
     * 1.遍历所有的像素
     * 2.从为值为1的像素开始向四个方向进行深度优先遍历，返回值为：1+四个方向的为1的结果
     * 3.当值为0，或者行数值或者列数值超过边界，则结束当前结点向下遍历的路径；当为1且在边界范围内,将该像素值设置为0，重复步骤2
     * 4.得到步骤：1当前像素上的面积大小，和已经遍历出的岛屿大小比较，得到最大值。
     *
     * @return
     */
    private int method1(int[][] grid){
        int max = 0;
        for (int r = 0; r < grid.length; r++){
            for (int c = 0; c < grid[0].length; c++){
                max = Math.max(max, dfs(grid, r, c));
            }
        }
        return max;
    }

    private int dfs(int[][] grid, int r, int c){
        //如果行数和列数都在边界值范围内，且像素值为1
        if(r >= 0 && r < grid.length && c >=0 && c < grid[0].length && grid[r][c] == 1){
            //已经统计过的结点置0
            grid[r][c] = 0;

            int num = 1;

            num += dfs(grid, r - 1, c);
            num += dfs(grid, r + 1, c);
            num += dfs(grid, r, c - 1);
            num += dfs(grid, r, c + 1);
            return num;
        }

        return 0;
    }

    private int method2(){
        int max = 0;

        return max;
    }

}
